import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 面试题 17.15. 最长单词
 * https://leetcode-cn.com/problems/longest-word-lcci/
 */
public class Solutions_mianshi_17_15 {
    public static void main(String[] args) {
//        String[] words = {"cat", "banana", "dog", "nana", "walk", "walker", "dogwalker"};
        // output: "dogwalker"

//        String[] words = {"mbzznzbccc", "zbmcbbcbze", "cbz", "cbzcbz"};  // output: "cbzcbz"

        String[] words = {"qlmql", "qlmqlmqqlqmqqlq", "mqqlqmqqlqmqqlq", "mqqlq", "mqqlqlmlsmqq",
                "qmlmmmmsm", "lmlsmqq", "slmsqq", "mslqssl", "mqqlqmqqlq"};  // output: "mqqlqmqqlqmqqlq"

//        String[] words = {"ikjkikkki", "ikjkikkknlkllkklni", "lkliki", "ininjkkkk", "ikjkikkk", "i",
//                            "ininjkkkknlkllkklni", "nlkllkklni", "j"};
        // output: "ininjkkkknlkllkklni"

        String result = longestWord(words);
        System.out.println(result);
    }

    public static TrieNode_17_15 root = null;
    /**
     * 解法二：前缀树（4ms）
     */
    public static String longestWord(String[] words) {
        if (words == null || words.length < 1) {
            return "";
        }
        // 将 words 数组排序，排序规则：按长度降序排列，长度相同按字典序升序排列
        Arrays.sort(words, (o1, o2) -> o1.length() == o2.length() ?
                o1.compareTo(o2) : o2.length() - o1.length());
        root = new TrieNode_17_15();
        // 构建前缀树
        for (String word : words) {
            char[] arr = word.toCharArray();
            buildTrie(arr);
        }
        // 排序后，最后一个单词的长度即是最短长度
        minLen = words[words.length - 1].length();
        // 排序后，遍历 words，对每个 word 进行 dfs 查找，若是匹配到 word 由多个单词组成，即是长度最大，同时字典序最小的
        for (String word : words) {
            char[] arr = word.toCharArray();
            if (find(arr, root, word, 0)) {
                return word;
            }
        }
        return "";
    }

    public static boolean find(char[] arr, TrieNode_17_15 root, String origin, int idx) {
        TrieNode_17_15 cur = root;
        for (int i = idx; i < arr.length; i++) {
            char c = arr[i];
            cur = cur.childs[c - 'a'];
            if (cur == null) {
                // 路径中没有字符 c，不用再比较后面的字符了
                break;
            }
            // 当前字符是否是一个单词的结束字符
            if (cur.word != null) {
                if (i == arr.length - 1 && !origin.equals(cur.word)) {
                    // 表示 origin 单词一定是由多个单词组合而成，return true
                    return true;
                }
                // 递归查找 [i + 1, len - 1] 区间的字符，是否可以组成一个单词，或者可以组成多个单词
                boolean res = find(arr, root, origin, i + 1);
                if (res) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void buildTrie(char[] arr) {
        TrieNode_17_15 cur = root;
        for (char c : arr) {
            if (cur.childs[c - 'a'] == null) {
                cur.childs[c - 'a'] = new TrieNode_17_15();
            }
            cur = cur.childs[c - 'a'];
        }
        cur.word = String.valueOf(arr);
    }

    // 记录下 words 中单词的最小长度
    private static int minLen = 0;
    private static Set<String> set = null;

    /**
     * 解法一：Set + 深度优先搜索（5ms）
     */
    public static String longestWord2(String[] words) {
        if (words == null || words.length < 1) {
            return "";
        }
        // 将 words 数组排序，排序规则：按长度降序排列，长度相同按字典序升序排列
        Arrays.sort(words, (o1, o2) -> o1.length() == o2.length() ?
                        o1.compareTo(o2) : o2.length() - o1.length());
        set = new HashSet<>();
        for (String word : words) {
            set.add(word);
        }
        // 排序后，最后一个单词的长度即是最短长度
        minLen = words[words.length - 1].length();
        // 排序后，遍历 words，对每个 word 进行 dfs 查找，若是匹配到 word 由多个单词组成，即是长度最大，同时字典序最小的
        for (int i = 0; i < words.length; i++) {
            // 先移除掉，防止一个单词的完全匹配，如果还能匹配到，那么一定是由多个单词组合匹配到的
            set.remove(words[i]);
            if (dfs(words[i])) {
                return words[i];
            }
            // 还需要添加上，供其他单词使用
            set.add(words[i]);
        }
        return "";
    }

    public static boolean dfs(String word) {
        if (set.contains(word)) {
            // 结束条件：当前 word 存在于 set 中
            return true;
        }
        // 剪枝效果：所截取的字符串长度，必然大于等于 minLen
        for (int i = minLen; i <= word.length() - minLen; i++) {
            // 截取前半段
            String before = word.substring(0, i);
            if (set.contains(before)) {
                // 前半段存在，判断后半段
                String after = word.substring(i);
                // 递归解决子问题：after 是否是一个单词，或者是一个组合单词
                boolean res = dfs(after);
                if (res) {
                    // after 是一个存在于 set 中的单词，或者 after 也是一个组合单词
                    // 那么 word 是由 before + after 组合而成
                    return true;
                }
            }
        }
        return false;
    }
}

class TrieNode_17_15 {
    String word;  // 从根节点到当前字符，路径能够表示的单词
    TrieNode_17_15[] childs;  // 子节点

    public TrieNode_17_15() {
        childs = new TrieNode_17_15[26];
    }
}
